Evolutionary algorithms (EA) have come to represent an important paradigm for solving or approximating the solutions to combinatorial optimization problems, especially hard optimization problems, e.g., the traveling salesman's problem. See, e.g., Zbigniew Michalewicz, Genetic Algorithms & Data Structures=Evolution Programs (Springer 1999).
To use the EA paradigm for a particular problem requires that possible solutions to the problem be parameterized by a data structure capable of the “genetic” operations to be described, and that the quality of the solution in the problem be represented by an objective (or “fitness”) function applied to the possible solution. Genetic algorithms (GA) are special cases of EAs where the data structure parameter is a fixed-length list of values. In classical GAs, the values are single bits. The data structure parameter defining a possible solution is known as a “chromosome,” and the individual elements of the data structure are known as “genes.”
Generally, EAs search for increasingly good (or “fit”) solutions, or even an optimal solution, by performing a number of repeated transformations or iterations on a collection of possible solutions. Each possible solution is known as an “individual”; the collection of possible solutions is known as a “population”; and each iteration is known as a “generation.” Generally, the number of individuals in a population is constant from generation and is an important EA parameter.
In more detail, each generation includes four basic steps. In a first step, the, individuals are selected from the general population for the next step. Selection of individuals may require global information to determine which individuals are chosen from the population. In the classic selection method, individuals are probabilistically selected based on their relative fitness with respect to the total fitness of the population. Thus, the higher the fitness, the more likely the individual would be selected for the next step. In another selection method, individuals are probabilistically selected based on fitness rank within the entire population (rank-based selection), or on fitness rank within a random sample of the population (tournament selection). In a further alternative, the more fit individuals in the population are selected (elitist selection).
Next, in a second step, the selected individuals are altered to form new individuals by performing genetic operations. In most cases, the genetic operators include “mutation,” in which part of the data structure parameterizing an individual is randomly changed, and “crossover,” in which portions of the parameterizing data structures of two individuals are exchanged. The frequencies of mutation and crossover (and how individuals are chosen for crossover) are further EA parameters. For example, in classical GAs where the data structure parameter is a bit string, mutation may flip one bit, while crossover may exchange portions of two strings.
In the third step, the fitness of all the new individuals in the population at the current generation is determined by applying the fitness (or objective) function.
In the last step, the individuals that will comprise the succeeding population are determined. The succeeding population is ordinarily formed in one of two ways. In generational reproduction, each new individual created by the second step replaces one of the parents, sometimes keeping the best parent (elitism). Alternatively, the generational reproduction method requires that the new individual must be better than both parents in order to remain, otherwise both parents remain. The other method is known as steady-state reproduction. In steady-state reproduction, both parents are retained, and the fitness evaluation performed in the third step determines which individuals in the whole population are the least fit. These least fit individuals are removed from the population, thus reducing the population to its original size.
An initial population of individuals may be created by simply randomly assigning content to the parameterizing data structure (the chromosomes). For classic GAs, bits in the bit string may be randomly set to zero or one.
Because EAs operate on populations of semi-independent individuals, they offer many opportunities for parallelization. In a simplest parallelization technique, computation of the fitness function for each individual, which is often the most computationally intensive part of an EA, may be done in parallel. Additional parallelization techniques are known in the art. See, e.g., Brick Cantu-Paz, Efficient and accurate parallel genetic algorithms (Kluwer Academic 2000), and Schmeck et al., Parallel implementations of evolutionary algorithms, in Solutions to Parallel and Distributed Computing Problems 47-68 (Zomaya et al. eds., Wiley 2001). In particular, the following three parallelization techniques are known.                The farming model: Here, the population selection step is performed on only one processor, while pairs of individuals are distributed to other processors for genetic alteration and the usually time-consuming fitness evaluation. This model is suited for systems with a small number of processors.        The island model: In this model, the population is divided into a number of “subpopulations.” Subpopulations are assigned to separate processors where they evolve independently, except for occasional exchanges of individuals between neighboring subpopulations. Subpopulations are neighboring if they are adjacent according to a chosen communication topology, for example a ring interconnection of the subpopulations. This model is suited to clusters of workstations, each powerful enough to process a whole subpopulation, and with relatively high bandwidth communication connections.        The diffusion model: Here, a spatial distribution is defined on all the individuals in the population, and selection is restricted to only those individuals in a local neighborhood. This model is suited to a highly parallel single instruction stream, multiple data stream computer, with each individual being assigned its own processor. Communication in this model is purely local, and the computational requirements on each node are limited.The latter two techniques are not formally exactly equivalent to the standard EA paradigm. Instead, in these latter models, the selection process has been distributed and localized (instead of operating on the population as a whole) in order to reduce inter-processor communication.        
However, the known parallelization techniques for EAs have been developed with particular parallel computing platforms in mind. In particular, these techniques expect that both processor and also inter-processor communication capabilities are preferably homogenous, or at least known in advance. Such expectations are met by, for example, dedicated massively parallel systems, or by dedicated local clusters of workstations on a local high-speed interconnection.
But some of the most ubiquitous parallel systems available currently, intranets or the Internet, meet none of these expectations. In particular, they have heterogeneous capabilities, have unpredictable processor availability, and have unpredictable and generally low communications bandwidth.                Heterogeneous capabilities: Usually, the computers connected to these networks are of widely differing capabilities, ranging from simple PCs to powerful workstations or mainframes.        Unpredictable availability: The connected computers may be otherwise used, and spare computing power available for other tasks, such as EA processing, is therefore unpredictable.        Low and unpredictable bandwidth: Different computers have vastly different network connections, ranging from direct connection to backbone to a slow analog modem. Overall, the connections are slow compared to connections within local clusters of computers.None of the known parallelization techniques are suited to these most common examples of parallel systems.        
For example, low and unpredictable communication bandwidth severely limits the use of both the farming model and the diffusion model, since these models have communication demands that require high and predictable bandwidth. Further, subpopulations that are local according to the selected topology may reside on real processors that are a considerable distance apart, further burdening the communications connections.
On the other hand, use of the island model is also severely limited by heterogeneous and unpredictable processor capabilities. Variable processor capabilities lead to highly uneven evolution of the separate subpopulations. Subpopulations on slower processors will evolve less rapid than subpopulations on a faster processor. Then, when individuals migrate from slower to faster processors, the immigrants will be generally less fit than the natives, and will be rapidly eliminated by selection. Thus, computing resources of the slower processors is effectively wasted. See, e.g., Branke, et al., A distributed genetic algorithm improving the generalization behavior of neural networks, in Machine Learning: ECML-95, 912 LNCS 107-21 (N. Lavrac and S. Wrobel, eds., Springer 1995).
What is needed, and what is lacking in the prior art, is a technique that exploits the natural parallelism in EAs in networks of heterogenous computers with heterogeneous and generally slow communications bandwidth.